第二类斯特林数

一.定义

第二类斯特林数 {nm}\begin{Bmatrix}n\\m\end{Bmatrix} 表示把 nn 个不同的小球放进 mm 个相同的盒子里,不能有空盒的方案数。

一些小性质:

  • {n0}=[n=0]\begin{Bmatrix}n\\0\end{Bmatrix}=[n=0]
  • n<mn<m{nm}=0\begin{Bmatrix}n\\m\end{Bmatrix}=0

二.一些等式

1. 递推式:{nm}={n1m1}+m{n1m}\begin{Bmatrix}n\\m\end{Bmatrix}=\begin{Bmatrix}n-1\\m-1\end{Bmatrix}+m\begin{Bmatrix}n-1\\m\end{Bmatrix}

对第 nn 个球的放法讨论

  1. 单独放一个盒子,方案为 {n1m1}\begin{Bmatrix}n-1\\m-1\end{Bmatrix}
  2. 与其他球放在一个盒子,因为盒子不同有 mm 种选法,每种选法方案为 {n1m}\begin{Bmatrix}n-1\\m\end{Bmatrix}

2.自然幂数和:mn=i=0n{ni}mi=i=0n{ni}(mi)i!m^n=\sum_{i=0}^n \begin{Bmatrix}n\\i\end{Bmatrix} m^{\underline i}=\sum_{i=0}^n \begin{Bmatrix}n\\i\end{Bmatrix} \binom{m}{i} i!

1.组合意义

左式为将 nn 不同的小球放进 mm 个不同的盒子里。

右式枚举非空盒子的数量 ii,选盒子的方案数为 (mi)\binom m i , 将 nn 个不同的球放入 ii 个盒子方案数为 {ni}\begin{Bmatrix}n\\i\end{Bmatrix},因为盒子不同所以有 i!i! 种排列。

2.例题

1.CF932E Team Work

2.P4091 [HEOI2016/TJOI2016]求和

3.P4827 [国家集训队] Crash 的文明世界 & SP7363 TREESUM - Tree Sum

4.CF961G Partitions

5.CF1097G

3.通项公式:{nm}=1m!i=0m(1)i(mi)(mi)n\begin{Bmatrix}n\\m\end{Bmatrix}= \frac{1}{m!}\sum_{i=0}^m \left(-1\right)^i \binom {m}{i} \left(m-i\right)^n

1.证明

f(m)=mn,g(m)={nm}m!f(m)=m^n,g(m)=\begin{Bmatrix}n\\m\end{Bmatrix} m!

那么有: f(m)=i=0m(mi){ni}i!=i=0m(mi)g(i)f(m)=\sum_{i=0}^m \binom m i \begin{Bmatrix}n\\i\end{Bmatrix} i!=\sum_{i=0}^m \binom m i g(i)

这里上界为 mm 不影响答案,因为 n<mn<m{ni}=0\begin{Bmatrix}n\\i\end{Bmatrix}=0

然后由二项式反演得: g(m)=i=0m(1)mi(mi)f(i)g(m)=\sum_{i=0}^m (-1)^{m-i}\binom m i f(i)

{nm}m!=i=0m(1)mi(mi)in\begin{Bmatrix}n\\m\end{Bmatrix} m!=\sum_{i=0}^m (-1)^{m-i}\binom m i i^n

{nm}=1m!i=0m(1)mi(mi)in\begin{Bmatrix}n\\m\end{Bmatrix}=\frac{1}{m!}\sum_{i=0}^m (-1)^{m-i}\binom m i i^n

{nm}=1m!i=0m(1)i(mi)(mi)n\begin{Bmatrix}n\\m\end{Bmatrix}=\frac{1}{m!}\sum_{i=0}^m (-1)^{i}\binom m i (m-i)^n

2.应用 P5395 第二类斯特林数·行

{nm}m!=i=0m(1)mi(mi)in\begin{Bmatrix}n\\m\end{Bmatrix} m!=\sum_{i=0}^m (-1)^{m-i}\binom m i i^n

{nm}m!=i=0m(1)mim!i!(mi)!in\begin{Bmatrix}n\\m\end{Bmatrix} m!=\sum_{i=0}^m (-1)^{m-i} \frac{m!}{i! (m-i)!} i^n

{nm}=i=0m(1)miini!(mi)!\begin{Bmatrix}n\\m\end{Bmatrix}=\sum_{i=0}^m \frac{(-1)^{m-i}i^n}{i!(m-i)!}

{nm}=i=0mini!(1)mi(mi)!\begin{Bmatrix}n\\m\end{Bmatrix}=\sum_{i=0}^m \frac{i^n}{i!} \frac{(-1)^{m-i}}{(m-i)!}

可以看出是一个卷积形式,用多项式乘法可 O(nlogn)\mathcal{O(n \log n)} 求出第二类斯特林数的任意一行。

三.生成函数